import java.util.Arrays;

public  class TestHeapMy{
        public int[] elem;
        public int usedSize;

        public TestHeapMy(){
            this.elem = new int[10];
        }

        //用一个数组初始化这个堆 , 让这个堆中开始有元素
        public void initElem(int[] array){
            for(int i = 0;i<array.length;i++){
                this.elem[i] = array[i];
                this.usedSize++;
            }
        }
        public void createHeap(){
            for(int parent = (usedSize-1)/2;parent>=0;parent--){
                siftDown(parent,this.usedSize);
            }
        }


        private void siftDown(int parent, int usedSize) {
            int child = parent*2+1;
            while(child<usedSize){
                if(child+1<usedSize&&elem[child]<elem[child+1])
                    child++;//让child指向较大值
                if(elem[parent]<elem[child]){//创建大根堆
                    swap(elem,parent,child);//交换
                    parent = child;
                    child = child*2+1;
                }else {
                    break;
                }
            }

        }
        public void swap(int[] elem,int i,int j ){
            int tmp = elem[i];
            elem[i] = elem[j];
            elem[j] = tmp;
        }
        public void siftUp(int child){
            int parent = (child-1)/2;
            while (parent>=0) {
                if (elem[child] > elem[parent]) {
                    swap(elem, parent, child);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else {
                    break;
                }
            }
        }
        public boolean isFull(){
            return usedSize == elem.length;

        }
        public void offer(int val){//在尾部增加元素
            if(isFull()){
                elem = Arrays.copyOf(elem,elem.length*2);
            }
            elem[usedSize] = val;//在最末尾添加元素
            siftUp(usedSize);//向上调整 先调整再++; 如果先++,则可能会超出范围
            usedSize++;
        }
        public boolean isEmpty(){
            return usedSize == 0;
        }
        public int  poll(){//删除顶层元素
            if(isEmpty()){
                return -1;
            }
            int val = elem[0];
            swap(elem,0,usedSize-1);//交换 0下标元素 和 最后一个元素
            siftDown(0,usedSize-1);//向下调整 不调整此时最后一个元素 , 因为该元素是要删除的元素,直接让usedSize--就好了
            usedSize--;
            return val;
        }
        public int peek() {//获取顶层元素
            if(isEmpty()) {
                return -1;
            }
            return elem[0];
        }
        public void heepSort(){//基于大根堆 , 完成升序排列
            int end = usedSize-1;
            while(end>0){
                swap(elem,0,end);//基于大根堆 , 顶层为最大值 , 将最大值放在末尾处 , 下一次循环将较大者放到end-1位置 , end位置是排序好的元素
                siftDown(0,end);//注意这个end是堆的大小 , 已经减过1了
                end--;//指向下一次末尾序号
            }
        }

    }

